package org.example.top40;

public class main04 {
    //数组中的第K个最大元素
    //分区：pivot要的是数组中的值（最好是随机的）最后重合的数组要pivot
    //分区返回的是下标low/high
    public static void main(String[] args) {
        int[] nums={3,2,3,1,2,4,5,5,6};
        int k=4;
        int target=findKnum(nums,k);
        System.out.println(target);
    }

    private static int findKnum(int[] nums, int k) {
        int low=0;
        int high=nums.length-1;
        quickSort(nums,low,high);
        return nums[nums.length-k];
    }
    private static void quickSort(int[] nums,int low,int high){
        if (low<high){
            int pi=partition(nums,low,high);
            quickSort(nums,low,pi-1);
            quickSort(nums,pi+1,high);
        }
    }
    public static int partition(int[] nums,int low,int high){
        int pivot=nums[low];
        while(low<high){
            while(low<high&&nums[high]>=pivot){
                high--;
            }
            nums[low]=nums[high];
            while (low<high&&nums[low]<=pivot){
                low++;
            }
            nums[high]=nums[low];
        }
        nums[low]=pivot;
        return low;
    }
}
